package com.sheng.leetcode.year2023.month06.day01;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/06/01
 * <p>
 * 2517. 礼盒的最大甜蜜度<p>
 * <p>
 * 给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。<p>
 * 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。<p>
 * 返回礼盒的 最大 甜蜜度。<p>
 * <p>
 * 示例 1：<p>
 * 输入：price = [13,5,1,8,21,2], k = 3<p>
 * 输出：8<p>
 * 解释：选出价格分别为 [13,5,21] 的三类糖果。<p>
 * 礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。<p>
 * 可以证明能够取得的最大甜蜜度就是 8 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：price = [1,3,1], k = 2<p>
 * 输出：2<p>
 * 解释：选出价格分别为 [1,3] 的两类糖果。<p>
 * 礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。<p>
 * 可以证明能够取得的最大甜蜜度就是 2 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：price = [7,7,7,7], k = 2<p>
 * 输出：0<p>
 * 解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。<p>
 * <p>
 * 提示：<p>
 * 1 <= price.length <= 10^5<p>
 * 1 <= price[i] <= 10^9<p>
 * 2 <= k <= price.length<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-tastiness-of-candy-basket">2517. 礼盒的最大甜蜜度</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2517 {

    @Test
    public void test01() {
        int[] price = {13, 5, 1, 8, 21, 2};
//        int[] price = {1, 3, 1};
        int k = 2;
        System.out.println(new Solution().maximumTastiness(price, k));
    }
}

class Solution {
    public int maximumTastiness(int[] price, int k) {
        // price[i] 表示第 i 类糖果的价格
        // 题目要求选出 k 种糖果，然后两两计算糖果之间的价格绝对差的最小值，即为该次的最大甜蜜度
        Arrays.sort(price);
        int n = price.length;
        int l = 0, r = price[n - 1] - price[0];
        while (l < r) {
            // 计算出中间值 mid 作为甜蜜度
            int mid = (l + r + 1) >> 1;
            // 判断是否可行
            if (check(price, k, mid)) {
                // 可行
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public boolean check(int[] price, int k, int x) {
        // cnt 表示当前已选取的糖果的数量
        // pre 表示上一个选取的糖果的价格
        int cnt = 0, pre = -x;
        for (int cur : price) {
            if (cur - pre >= x) {
                // 满足条件则选取这个糖果，然后更新 pre
                pre = cur;
                cnt++;
            }
        }
        return cnt >= k;
    }
}
